package 力扣._102_二叉树的层序遍历;

import 力扣.公用数据结构.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;
        queue.add(root);

        int now = 1, next = 0, count = 0;
        List<Integer> t = new ArrayList<>();
        while (!queue.isEmpty()) {      //也可以先记录当前队列大小，遍历指定大小后再新建数组
            TreeNode poll = queue.poll();
            t.add(poll.val);
            count++;
            if (poll.left != null) {
                queue.add(poll.left);
                next++;
            }
            if (poll.right != null) {
                queue.add(poll.right);
                next++;
            }
            if (count == now) {    //当前层遍历结束
                result.add(t);
                t = new ArrayList<>();
                now = next;
                count = 0;
                next = 0;
            }

        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.creat("[]");
        List<List<Integer>> lists = new Solution().levelOrder(node);
        System.out.println(lists);
    }
}
